{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Palindrome Linked List LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #recursion #linked-list #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #递归 #链表 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isPalindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #回文链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>编写一个函数，检查输入的链表是否是回文的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入： </strong>1-&gt;2\n",
    "<strong>输出：</strong> false \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入： </strong>1-&gt;2-&gt;2-&gt;1\n",
    "<strong>输出：</strong> true \n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong><br>\n",
    "你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [palindrome-linked-list-lcci](https://leetcode.cn/problems/palindrome-linked-list-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [palindrome-linked-list-lcci](https://leetcode.cn/problems/palindrome-linked-list-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2]', '[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head:\n",
    "            return True\n",
    "        if not head.next:\n",
    "            return True\n",
    "        pf = pl = head\n",
    "        l = []\n",
    "        flag = 1\n",
    "        while pf.next:\n",
    "            l.append(pl.val)\n",
    "            pl = pl.next\n",
    "            pf = pf.next.next\n",
    "            if not pf:\n",
    "                flag = 0\n",
    "                break\n",
    "        if flag:\n",
    "            pl = pl.next\n",
    "        while pl:\n",
    "            if pl.val != l.pop():\n",
    "                return False\n",
    "            pl = pl.next\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "\n",
    "        values = []\n",
    "\n",
    "        cur = head\n",
    "        while cur:\n",
    "            values.append(cur.val)\n",
    "            cur = cur.next\n",
    "        \n",
    "        print(values)\n",
    "        return values == values[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        cur = head\n",
    "        temp = []\n",
    "        while cur != None:\n",
    "            temp.append(str(cur.val))\n",
    "            cur = cur.next\n",
    "        if temp[::] == temp[::-1]:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head: return True\n",
    "        def rev(head):\n",
    "            if head.next is None: return head\n",
    "            dummy = ListNode(-1,head)\n",
    "            rev_tail = head\n",
    "            while (to_rev := rev_tail.next) is not None:\n",
    "                nxt = to_rev.next\n",
    "                rev_tail.next = nxt\n",
    "                origin_head = dummy.next\n",
    "                dummy.next = to_rev\n",
    "                to_rev.next = origin_head\n",
    "            return dummy.next\n",
    "        def pp(node_input):\n",
    "            node = node_input\n",
    "            res = []\n",
    "            while node:\n",
    "                res.append(node.val)\n",
    "                node = node.next\n",
    "            print('，'.join(map(str,res)))\n",
    "        # find half\n",
    "        fast = slow = head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "        pp(fast)\n",
    "        pp(slow)\n",
    "        rev_head = rev(slow)\n",
    "        cur,rev_cur = head,rev_head \n",
    "        pp(cur)\n",
    "        pp(rev_cur)\n",
    "        while rev_cur and cur:\n",
    "            if rev_cur.val != cur.val: return False\n",
    "            rev_cur,cur = rev_cur.next,cur.next\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head:\n",
    "            return True\n",
    "        \n",
    "        node = head\n",
    "        c = 0\n",
    "        while node:\n",
    "            c += 1\n",
    "            node = node.next\n",
    "        \n",
    "        sign = c & 1\n",
    "        c >>= 1\n",
    "        for _ in range(c):\n",
    "            head.next.prev = head\n",
    "            head = head.next\n",
    "            del head.prev.next\n",
    "        if sign:\n",
    "            node = head\n",
    "            for _ in range(c):\n",
    "                head = head.next\n",
    "                node = node.prev\n",
    "                if head.val != node.val:\n",
    "                    return False\n",
    "            return True\n",
    "        else:\n",
    "            node = head.prev\n",
    "            for _ in range(c-1):\n",
    "                if head.val != node.val:\n",
    "                    return False\n",
    "                head = head.next\n",
    "                node = node.prev\n",
    "            \n",
    "            return head.val == node.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        fast=head\n",
    "        slow=head\n",
    "        while fast and fast.next:\n",
    "            slow=slow.next\n",
    "            fast=fast.next.next\n",
    "        if not slow:\n",
    "            return True\n",
    "        last = ListNode(slow.val)\n",
    "        cover = slow\n",
    "        while slow and slow.next:\n",
    "            slow = slow.next\n",
    "            cover = ListNode(slow.val)\n",
    "            cover.next = last\n",
    "            last = cover\n",
    "        while cover:\n",
    "            if cover.val!=head.val:\n",
    "                return False\n",
    "            cover=cover.next\n",
    "            head=head.next\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if head is None:\n",
    "            return True\n",
    "            \n",
    "        ptr, slow, fast = ListNode(), ListNode(), ListNode()\n",
    "        ptr.next, slow.next, fast.next = head, head, head\n",
    "        while fast is not None and fast.next is not None:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            # reverse left part\n",
    "            next = ptr.next\n",
    "            ptr.next = ListNode(slow.val)\n",
    "            ptr.next.next = next \n",
    "\n",
    "        if fast is None:\n",
    "            ptr.next = ptr.next.next\n",
    "\n",
    "        while ptr.next is not None and slow.next is not None:\n",
    "            ptr = ptr.next\n",
    "            slow = slow.next\n",
    "            if ptr.val != slow.val:\n",
    "                return False\n",
    "        \n",
    "        return ptr.next is not None or slow.next is not None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        value = {}\n",
    "        count = 0\n",
    "        while head:\n",
    "            \n",
    "            value.update({count : head.val})\n",
    "            head = head.next\n",
    "            count +=1\n",
    "        #print(value)\n",
    "        left, right = 0, (count-1)\n",
    "        while left <= right:\n",
    "            if value.get(left) != value.get(right):\n",
    "                #print(left, right)\n",
    "                return False\n",
    "            left +=1\n",
    "            right -=1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        # reverse node\n",
    "        rev = None\n",
    "        curr = head\n",
    "        while(curr):\n",
    "            temp = ListNode(curr.val)\n",
    "            temp.next = rev\n",
    "            rev = temp\n",
    "            curr=curr.next\n",
    "\n",
    "        while(head):\n",
    "            if(head.val != rev.val):\n",
    "                return False\n",
    "            head = head.next\n",
    "            rev = rev.next\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        L = None\n",
    "        p=head\n",
    "        while p is not None:\n",
    "            q=ListNode(val=p.val)\n",
    "            q.next=L \n",
    "            L=q\n",
    "            p=p.next\n",
    "        p=head\n",
    "        while p and L:\n",
    "            if p.val != L.val:\n",
    "                return False\n",
    "            else:\n",
    "                p=p.next\n",
    "                L=L.next\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        def reverse():\n",
    "            nh = None \n",
    "            cur = head\n",
    "            while cur:\n",
    "                ln = ListNode(cur.val)\n",
    "                ln.next = nh\n",
    "                nh = ln\n",
    "                cur = cur.next\n",
    "            return nh \n",
    "        nh = reverse()\n",
    "        c1, c2 = head, nh\n",
    "        while c1 and c2:\n",
    "            if c1.val != c2.val:\n",
    "                return False\n",
    "            c1, c2 = c1.next, c2.next\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        def judge(a,b):\n",
    "            if a and b:\n",
    "                if a.val==b.val:\n",
    "                    return judge(a.next,b.next)\n",
    "            elif a==None and b==None:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        if not head: return True\n",
    "        if not head.next: return True\n",
    "        first=ListNode(head.val)\n",
    "        f=first\n",
    "        second=head.next\n",
    "        while first and second:\n",
    "            # print(first,'\\n',second)\n",
    "            if judge(first,second):\n",
    "                return True\n",
    "            f=ListNode(second.val)\n",
    "            f.next=first\n",
    "            second=second.next\n",
    "            if second and judge(first,second):\n",
    "                return True\n",
    "            first=f\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head or not head.next:\n",
    "            return True\n",
    "        slow, fast, last = head, head.next, None\n",
    "        while fast.next and fast.next.next:\n",
    "            tmp = slow.next\n",
    "            slow.next = last if last else None\n",
    "            last = slow\n",
    "            slow = tmp\n",
    "            fast = fast.next.next\n",
    "        middle = slow.next.next if fast.next else slow.next # 区分链表长度为奇数偶数的情况,middle为后半段的开始\n",
    "        slow.next = last #完成前半段翻转\n",
    "        while middle:\n",
    "            if slow.val != middle.val:\n",
    "                return False\n",
    "            slow, middle = slow.next, middle.next\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        def find_half(head):\n",
    "            slow,fast=head,head\n",
    "            while fast.next and fast.next.next:\n",
    "                slow=slow.next\n",
    "                fast=fast.next.next\n",
    "            return slow\n",
    "        def reverseList(head):\n",
    "            prev=None\n",
    "            cur=head\n",
    "            while cur:\n",
    "                temp=cur.next\n",
    "                cur.next=prev\n",
    "                prev=cur\n",
    "                cur=temp\n",
    "            return prev\n",
    "        if not head or not head.next:\n",
    "            return True\n",
    "        half_p=find_half(head)\n",
    "        after_r=reverseList(half_p.next)\n",
    "        p=head\n",
    "        q=after_r\n",
    "        while q:\n",
    "            if p.val!=q.val:\n",
    "                return False\n",
    "            p=p.next\n",
    "            q=q.next\n",
    "        return True\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head:\n",
    "            return True\n",
    "        ans=[]\n",
    "        p=head\n",
    "        while p:\n",
    "            ans.append(p.val)\n",
    "            p=p.next\n",
    "        print(ans)\n",
    "\n",
    "        if ans==ans[::-1]:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head or not head.next :\n",
    "            return True\n",
    "        \n",
    "        ans = []\n",
    "\n",
    "        while head:\n",
    "            ans.append(head.val)\n",
    "            head = head.next\n",
    "        \n",
    "        return self.palindromeFind(ans, 0)\n",
    "            \n",
    "    def palindromeFind(self, list, i):\n",
    "        if len(list)-1-i == i or (len(list)-1-i == i+1 and list[len(list)-1-i] == list[i]):\n",
    "            return True\n",
    "        elif len(list)-1-i<i or list[i] != list[len(list)-1-i]:\n",
    "            return False\n",
    "        return self.palindromeFind(list, i+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head or not head.next:\n",
    "            return True\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "        slow, fast = dummy, dummy\n",
    "        while fast.next and fast.next.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        head1 = head\n",
    "        # 奇数情况\n",
    "        if fast.next:\n",
    "            head2 = slow.next.next\n",
    "            slow.next = None\n",
    "        else:\n",
    "            head2 = slow.next\n",
    "            slow.next = None\n",
    "        # 反转链表\n",
    "        head3 = self.reverse(head2)\n",
    "        # 比较 head1 和 head3\n",
    "        return self.isSame(head1, head3)\n",
    "    \n",
    "    def reverse(self, head):\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        pre = None\n",
    "        while head:\n",
    "            nex = head.next\n",
    "            head.next = pre\n",
    "            pre = head\n",
    "            head = nex\n",
    "        return pre\n",
    "    \n",
    "    def isSame(self, head1, head2):\n",
    "        if not head1 and not head2:\n",
    "            return True\n",
    "        if not head1 or not head2:\n",
    "            return False\n",
    "        if head1.val != head2.val:\n",
    "            return False\n",
    "        return self.isSame(head1.next, head2.next)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head: return True\n",
    "\n",
    "        slow, fast = head, head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "\n",
    "        right = self.reverse(slow)\n",
    "        while head and right:\n",
    "            if head.val != right.val:\n",
    "                return False\n",
    "            head = head.next\n",
    "            right = right.next\n",
    "        return True\n",
    "\n",
    "    def reverse(self, head):\n",
    "        if not head.next: return head\n",
    "\n",
    "        cur = self.reverse(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head or not head.next: return True\n",
    "        po = ListNode(0)\n",
    "        po.next=head\n",
    "        slow = fast = po\n",
    "        while fast and fast.next:\n",
    "            slow =slow.next\n",
    "            fast=fast.next.next\n",
    "        node =head\n",
    "        slow = self.rever(slow.next)\n",
    "        while slow:\n",
    "            if slow.val != node.val:\n",
    "                return False\n",
    "            slow =slow.next\n",
    "            node = node.next\n",
    "        return True\n",
    "\n",
    "    def rever(self,node):\n",
    "        if not node.next:\n",
    "            return node\n",
    "        head=self.rever(node.next)\n",
    "        node.next.next=node\n",
    "        node.next = None\n",
    "        return head\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head:\n",
    "            return True\n",
    "        lst = [head.val]\n",
    "        while head.next:\n",
    "            lst.append(head.next.val)\n",
    "            head.next = head.next.next\n",
    "\n",
    "        def fun(lst,i,j):\n",
    "            if j-i<=0:\n",
    "                return True\n",
    "            else:\n",
    "                return fun(lst,i+1,j-1) and (lst[i]==lst[j])\n",
    "        \n",
    "        return fun(lst,0,len(lst)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindromeSub(self, node, pos):\n",
    "        if pos < (self.m-1)//2:\n",
    "            flag = self.isPalindromeSub(node.next, pos+1)\n",
    "            flag = flag and node.val == self.q.val\n",
    "            self.q = self.q.next\n",
    "            return flag\n",
    "        else:\n",
    "            self.q = node.next\n",
    "            if self.m%2 == 1:\n",
    "                return True\n",
    "            else:\n",
    "                flag = node.val == self.q.val\n",
    "                self.q = self.q.next\n",
    "                return flag\n",
    "\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head:\n",
    "            return True\n",
    "        p = head\n",
    "        self.m = 0\n",
    "        while p:\n",
    "            self.m += 1\n",
    "            p = p.next\n",
    "        \n",
    "        self.q = head\n",
    "        flag = self.isPalindromeSub(head, 0)\n",
    "        return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head:\n",
    "            return True\n",
    "        if not head.next:\n",
    "            return True\n",
    "        # 快慢指针\n",
    "        cur1 = head\n",
    "        cur2 = head\n",
    "        while cur2.next and cur2.next.next:\n",
    "            cur1 = cur1.next\n",
    "            cur2 = cur2.next.next\n",
    "        self.head1=cur1\n",
    "        if cur2.next:\n",
    "            self.head2 = cur1.next\n",
    "        else:\n",
    "            self.head2 = cur1\n",
    "        #  倒序遍历查看是否相等\n",
    "        return self.reverse(head)\n",
    "    def reverse(self,head):\n",
    "        if head is self.head1:\n",
    "            if self.head2 and head.val ==self.head2.val:\n",
    "                self.head2 = self.head2.next\n",
    "                return True\n",
    "            return False\n",
    "        next_is = self.reverse(head.next)\n",
    "        if next_is:\n",
    "            if self.head2.val ==head.val:\n",
    "                self.head2 = self.head2.next\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head or not head.next:\n",
    "            return True\n",
    "        \n",
    "        if head.next.next == None:\n",
    "            return head.val == head.next.val\n",
    "        \n",
    "        slow = head\n",
    "        fast = head\n",
    "\n",
    "        while fast.next and fast.next.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "\n",
    "        right = self.reverse(slow.next)\n",
    "        left = head\n",
    "        while right:\n",
    "            if right.val != left.val:\n",
    "                return False\n",
    "\n",
    "            right = right.next\n",
    "            left = left.next\n",
    "        \n",
    "        return True\n",
    "\n",
    "\n",
    "    def reverse(self, head):\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "\n",
    "        cur = self.reverse(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return cur\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def _base(self, slow, fast):\n",
    "        if fast.next is None:\n",
    "            return True, slow.next\n",
    "        if fast.next.next is None:\n",
    "            return slow.val == slow.next.val, slow.next.next\n",
    "        res = self._base(slow.next, fast.next.next)\n",
    "        ret = res[0]\n",
    "        if ret is False:\n",
    "            return False, None\n",
    "        return slow.val == res[1].val, res[1].next\n",
    "\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head or head and head.next is None:\n",
    "            return True\n",
    "\n",
    "        return self._base(head, head)[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def length(self, head):\n",
    "        len = 0\n",
    "        while head != None:\n",
    "            len += 1\n",
    "            head = head.next\n",
    "        return len\n",
    "\n",
    "    def isPalindromeRecurse(self, head, len):\n",
    "        if head == None or len <= 0:\n",
    "            return head, True\n",
    "        elif len == 1:\n",
    "            return head.next, True\n",
    "        \n",
    "        node, res = self.isPalindromeRecurse(head.next, len - 2)\n",
    "\n",
    "        if not res or node == None:\n",
    "            return node, res\n",
    "\n",
    "        res = head.val == node.val\n",
    "        node = node.next\n",
    "\n",
    "        return node, res\n",
    "\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        len = self.length(head)\n",
    "        node, res = self.isPalindromeRecurse(head, len)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        \n",
    "        # 队列，n，n\n",
    "        # s = deque()\n",
    "        # while head:\n",
    "        #     s.append(head.val)\n",
    "        #     head = head.next\n",
    "        # l = len(s)\n",
    "        # if l == 1:return True\n",
    "        # if l == 2:return s[0] == s[1]\n",
    "        # while l>1:\n",
    "        #     l -= 2\n",
    "        #     a,b = s.popleft(),s.pop()\n",
    "        #     if a!=b:return False\n",
    "        # return True\n",
    "\n",
    "        # 快慢指针 + 递归反转 n，1\n",
    "        # 1.具体来说，先通过快慢指针找到链表中点\n",
    "        # 2.然后使用递归反转将后一半链表反转\n",
    "        # 3.再对链表前半部分和后半部分逐节点进行比较\n",
    "        # 4.最后恢复后半链表，输出结果\n",
    "        if not head or not head.next:return True \n",
    "        # 1.\n",
    "        slow,fast = head,head.next\n",
    "        while fast:\n",
    "            fast = fast.next\n",
    "            if fast:\n",
    "                fast = fast.next\n",
    "                slow = slow.next\n",
    "            else:\n",
    "                break\n",
    "        # slow对应中点，如果链表长为奇数，那么slow就是中点节点，否则slow是前一半的最后一个节点\n",
    "        # 2.\n",
    "        def rever(node):\n",
    "            if not node or not node.next:\n",
    "                return node\n",
    "            p = rever(node.next)\n",
    "            node.next.next = node\n",
    "            node.next = None\n",
    "            return p\n",
    "        # 3.\n",
    "        r = rever(slow.next)\n",
    "        slow.next = None\n",
    "        rh = r\n",
    "        p = head\n",
    "        while r:\n",
    "            if p.val != r.val:\n",
    "                return False\n",
    "            p = p.next\n",
    "            r = r.next\n",
    "        # 4.\n",
    "        v = rever(rh)\n",
    "        slow.next = v\n",
    "        return True\n",
    "            \n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        p = head\n",
    "        length = 0\n",
    "        while p:\n",
    "            p = p.next\n",
    "            length += 1\n",
    "        \n",
    "        mid = length // 2\n",
    "        if length % 2 == 1:\n",
    "            mid += 1\n",
    "        mid_node = head\n",
    "        for _ in range(mid):\n",
    "            mid_node = mid_node.next\n",
    "        \n",
    "        mid_node = self.reverse(mid_node)\n",
    "        slow, fast = head, mid_node\n",
    "        while fast:\n",
    "            if slow.val != fast.val:\n",
    "                return False\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "        \n",
    "        return True\n",
    "    \n",
    "    def reverse(self, head):\n",
    "        if not head:\n",
    "            return None\n",
    "        if not head.next:\n",
    "            return head\n",
    "        last = self.reverse(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return last\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head:\n",
    "            return True\n",
    "        p = head\n",
    "        length = 0\n",
    "        while p:\n",
    "            p = p.next\n",
    "            length += 1\n",
    "        \n",
    "        mid = length // 2\n",
    "        if length % 2 == 1:\n",
    "            mid += 1\n",
    "        mid_node = head\n",
    "        for _ in range(mid):\n",
    "            mid_node = mid_node.next\n",
    "        \n",
    "        _, flag = self.check(head, mid_node)\n",
    "        return flag\n",
    "        \n",
    "    def check(self, l1, l2):\n",
    "        if not l2:\n",
    "            return l1, True\n",
    "        if not l2.next:\n",
    "            flag = l2.val == l1.val\n",
    "            return l1.next, flag\n",
    "        l1, last = self.check(l1, l2.next)\n",
    "        return l1.next, last and l1.val == l2.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        def reverse(cur,pre):\n",
    "            if not cur:\n",
    "                return pre\n",
    "            tmp = cur.next\n",
    "            cur.next = pre\n",
    "            return reverse(tmp,cur)\n",
    "\n",
    "        if not head:\n",
    "            return True\n",
    "        if head.next is None:\n",
    "            return True\n",
    "        if head.next.next is None:\n",
    "            return head.val == head.next.val\n",
    "        slow = fast = head\n",
    "        while fast.next and fast.next.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        slow.next = reverse(slow.next,None)\n",
    "        p1 = head\n",
    "        p2 = slow.next\n",
    "        while p2:\n",
    "            if p1.val != p2.val:\n",
    "                return False\n",
    "            p1 = p1.next\n",
    "            p2 = p2.next\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool: \n",
    "        def findMid(head: ListNode):\n",
    "            slow, fast = head, head.next.next\n",
    "            while fast and fast.next:\n",
    "                slow = slow.next\n",
    "                fast = fast.next.next\n",
    "            res = slow.next\n",
    "            slow.next = None\n",
    "            return res\n",
    "\n",
    "        def reverse(head: ListNode):\n",
    "            if not head or not head.next:\n",
    "                return head\n",
    "            tail = reverse(head.next)\n",
    "            head.next.next = head\n",
    "            head.next = None\n",
    "            return tail\n",
    "\n",
    "        if not head or not head.next:\n",
    "            return True\n",
    "        mid = findMid(head)\n",
    "        revMid = reverse(mid)\n",
    "        p = head\n",
    "        while revMid and p:\n",
    "            if revMid.val != p.val:\n",
    "                return False\n",
    "            else:\n",
    "                revMid = revMid.next\n",
    "                p = p.next\n",
    "        return True\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        slow, fast = head, head\n",
    "        while fast and fast.next :\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        rev = self.reverse(slow)\n",
    "        p = head\n",
    "        while rev:\n",
    "            if p.val != rev.val:\n",
    "                return False\n",
    "            else:\n",
    "                p = p.next\n",
    "                rev = rev.next\n",
    "        return True\n",
    "    def reverse(self, head:ListNode) -> ListNode:\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        res = self.reverse(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Result:\n",
    "    def __init__(self, node,length):\n",
    "        self.node = node\n",
    "        self.res = True\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        def getLength(head):\n",
    "            res = 0\n",
    "            while head:\n",
    "                res += 1\n",
    "                head = head.next\n",
    "            return res\n",
    "        \n",
    "        def isPalindromeRecurse(head, length):\n",
    "            if not head or length <=0:\n",
    "                return Result(head, True) # 到中间位置了，并且长度为偶数\n",
    "            \n",
    "            elif length == 1:   # 到中间位置并且长度为奇数，返回后半部分第一个\n",
    "                return Result(head.next, True)\n",
    "\n",
    "            else: \n",
    "                res = isPalindromeRecurse(head.next, length-2)\n",
    "                if not res.res or res.node == None:\n",
    "                    return res\n",
    "\n",
    "                res.res = (head.val == res.node.val)\n",
    "                res.node = res.node.next\n",
    "                return res \n",
    "\n",
    "        length = getLength(head)\n",
    "        res = isPalindromeRecurse(head, length)\n",
    "        return res.res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head or not head.next:\n",
    "            return True\n",
    "        s_p = f_p = head\n",
    "        while True:\n",
    "            if not f_p:\n",
    "                self.odd_flag = False\n",
    "                break\n",
    "            elif f_p.next:\n",
    "                s_p = s_p.next\n",
    "                f_p = f_p.next.next\n",
    "            else:\n",
    "                self.odd_flag = True\n",
    "                break\n",
    "        mid_node = s_p\n",
    "        node = head\n",
    "        def palindrome(node,mid_node):\n",
    "            if node.next == mid_node:\n",
    "                if self.odd_flag:\n",
    "                    return node.val == mid_node.next.val, mid_node.next.next\n",
    "                else:\n",
    "                    return node.val == mid_node.val,mid_node.next\n",
    "            flag, re_node = palindrome(node.next,mid_node)\n",
    "            return flag and re_node.val == node.val, re_node.next\n",
    "        flag, re_node = palindrome(node,mid_node)\n",
    "        return flag\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head or not head.next:\n",
    "            return True\n",
    "        s_p = f_p = head\n",
    "        while True:\n",
    "            if not f_p:\n",
    "                self.odd_flag = False\n",
    "                break\n",
    "            elif f_p.next:\n",
    "                s_p = s_p.next\n",
    "                f_p = f_p.next.next\n",
    "            else:\n",
    "                self.odd_flag = True\n",
    "                break\n",
    "        mid_node = s_p\n",
    "        node = head\n",
    "        def palindrome(node,mid_node):\n",
    "            if node.next == mid_node:\n",
    "                if self.odd_flag:\n",
    "                    return node.val == mid_node.next.val, mid_node.next.next\n",
    "                else:\n",
    "                    return node.val == mid_node.val,mid_node.next\n",
    "            flag, re_node = palindrome(node.next,mid_node)\n",
    "            return flag and re_node.val == node.val, re_node.next\n",
    "        flag, re_node = palindrome(node,mid_node)\n",
    "        return flag\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "            \n",
    "        return self.func([head],head)\n",
    "        \n",
    "\n",
    "\n",
    "    def func(self, p, head):\n",
    "\n",
    "        if not head:\n",
    "            return True\n",
    "\n",
    "        if self.func(p, head.next) == False:\n",
    "            return False\n",
    "\n",
    "\n",
    "        if head:\n",
    "            if p[0].val != head.val:\n",
    "                return False\n",
    "            else:\n",
    "                p[0] = p[0].next\n",
    "                return True\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "            \n",
    "        return self.func([head],head)\n",
    "        \n",
    "\n",
    "\n",
    "    def func(self, p, q):\n",
    "\n",
    "        if not q:\n",
    "            return True\n",
    "\n",
    "        if self.func(p, q.next) == False:\n",
    "            return False\n",
    "\n",
    "\n",
    "\n",
    "        if p[0].val != q.val:\n",
    "            return False\n",
    "        else:\n",
    "            p[0] = p[0].next\n",
    "            return True\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        def f(node: ListNode):\n",
    "            if not node or not node.next:\n",
    "                return node\n",
    "            res = f(node.next)\n",
    "            node.next.next = node\n",
    "            node.next = None\n",
    "            return res\n",
    "        fast = slow = head\n",
    "        while fast and fast.next and fast.next.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "        rev = f(slow.next) if slow else None\n",
    "        while head and rev:\n",
    "            if head.val == rev.val:\n",
    "                head = head.next\n",
    "                rev = rev.next\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    front = None\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        self.front = head\n",
    "        return self.checkPalindrome(head)\n",
    "\n",
    "    def checkPalindrome(self, head):\n",
    "        if not head:\n",
    "            return True\n",
    "        b_p = self.checkPalindrome(head.next) and head.val == self.front.val\n",
    "        self.front = self.front.next\n",
    "        return b_p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        self.flag=True\n",
    "        self.root=head\n",
    "        self.dfs(head)\n",
    "        return self.flag\n",
    "    def dfs(self,head):\n",
    "        if not head:\n",
    "            return ;\n",
    "        self.dfs(head.next)\n",
    "\n",
    "        if head.val!=self.root.val:\n",
    "            self.flag=False\n",
    "        self.root=self.root.next\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        self.arr1 = []\n",
    "        self.arr2 = []\n",
    "        self.preorder(head)\n",
    "        self.postorder(head)\n",
    "        return self.arr1 == self.arr2\n",
    "    def preorder(self,head):\n",
    "        if not head:\n",
    "            return None\n",
    "        self.arr1.append(head.val)\n",
    "        self.preorder(head.next)\n",
    "    def postorder(self,head):\n",
    "        if not head:\n",
    "            return None\n",
    "        self.postorder(head.next)\n",
    "        self.arr2.append(head.val)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head):\n",
    "        arr = (self.preorder(head))\n",
    "        left,right = 0,len(arr) - 1\n",
    "        while left < right:\n",
    "            if arr[left] != arr[right]:\n",
    "                return False\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        return True\n",
    "    \n",
    "    def preorder(self,head):\n",
    "        if not head:\n",
    "            return []\n",
    "        return [head.val] + self.preorder(head.next)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        node1 = head\n",
    "        node2 = head\n",
    "        return self._search(node1) == self._search2(node2)\n",
    "\n",
    "    def _search(self, head):\n",
    "        if not head:\n",
    "            return \"\"\n",
    "        ans = self._search(head.next)\n",
    "        return ans + str(head.val)\n",
    "\n",
    "    def _search2(self, head):\n",
    "        if not head:\n",
    "            return \"\"\n",
    "        ans = str(head.val)\n",
    "        return ans + self._search2(head.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head):\n",
    "        return self.preorder(head) == self.preorder(head)[::-1]\n",
    "    \n",
    "    def preorder(self,head):\n",
    "        if not head:\n",
    "            return []\n",
    "        return [head.val] + self.preorder(head.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        self.front_pointer = head\n",
    "        \n",
    "        def recursively_check(current_node=head):\n",
    "            if current_node is not None:\n",
    "                if not recursively_check(current_node.next):\n",
    "                    return False\n",
    "                if self.front_pointer.val != current_node.val:\n",
    "                    return False\n",
    "                self.front_pointer = self.front_pointer.next\n",
    "            return True\n",
    "\n",
    "        return recursively_check()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        self.front = head\n",
    "        def recursive(cur):\n",
    "            \"\"\"判断是否是回文链表\"\"\"\n",
    "            if cur is None:\n",
    "                return True\n",
    "            if not recursive(cur.next):\n",
    "                return False\n",
    "            elif self.front.val != cur.val:\n",
    "                return False\n",
    "            else:\n",
    "                self.front = self.front.next\n",
    "                return True\n",
    "        return recursive(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def flip(self, head):\n",
    "        if not head.next:\n",
    "            return head\n",
    "\n",
    "        new_head = self.flip(head.next)\n",
    "        # print(head.val)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return new_head\n",
    "        \n",
    "    def list_show(self, head):\n",
    "        res = []\n",
    "        while head:\n",
    "            res.append(head.val)\n",
    "            head = head.next\n",
    "        return res\n",
    "\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        res = True\n",
    "        origin_list = self.list_show(head)\n",
    "        if not head:\n",
    "            return res\n",
    "        elif not head.next:\n",
    "            return res\n",
    "        elif not head.next.next:\n",
    "            if head.val == head.next.val:\n",
    "                return res\n",
    "            else:\n",
    "                res = False\n",
    "                return res\n",
    "\n",
    "        fliped_head = self.flip(head)\n",
    "        fliped_list = self.list_show(fliped_head)\n",
    "        for i in range(len(origin_list)):\n",
    "            if origin_list[i] != fliped_list[i]:\n",
    "                res = False\n",
    "                break\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        self.front_pointer=head\n",
    "        def recursively_check(current_node=head):\n",
    "            if current_node is not None:\n",
    "                if not recursively_check(current_node.next):\n",
    "                    return False\n",
    "                if self.front_pointer.val!=current_node.val:\n",
    "                    return False\n",
    "                self.front_pointer=self.front_pointer.next\n",
    "            return True\n",
    "        return recursively_check()\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # self.front_pointer = head\n",
    "\n",
    "        # def recursively_check(current_node=head):\n",
    "        #     if current_node is not None:\n",
    "        #         if not recursively_check(current_node.next):\n",
    "        #             return False\n",
    "        #         if self.front_pointer.val != current_node.val:\n",
    "        #             return False\n",
    "        #         self.front_pointer = self.front_pointer.next\n",
    "        #     return True\n",
    "\n",
    "        # return recursively_check()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        # 递归函数外的指针\n",
    "        self.front_pointer = head\n",
    "        \n",
    "        # 递归函数\n",
    "        def recursively_check(cur = head):\n",
    "            if cur:\n",
    "                # 反向迭代节点\n",
    "                if not recursively_check(cur.next):\n",
    "                    return False\n",
    "                if self.front_pointer.val != cur.val:\n",
    "                    return False\n",
    "                # 递归函数外的变量向前迭代\n",
    "                self.front_pointer = self.front_pointer.next\n",
    "            return True\n",
    "        \n",
    "        return recursively_check()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        self.front = head\n",
    "        def check(node):\n",
    "            if not node:\n",
    "                return True\n",
    "            if not check(node.next):\n",
    "                return False\n",
    "            if node.val != self.front.val:\n",
    "                return False\n",
    "            self.front = self.front.next\n",
    "            return True\n",
    "        return check(head)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
